public class InsertSort {
    public static void main(String[] args) {
//        int[] arr = {6,5,7,3,9,8,5,2};
        int[] arr = {1, 1, 1, 1, 1};
        insertionSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    private static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int index = i-1;
            while (index >= 0) {
                if (arr[index] > tmp) {
                    arr[index+1] = arr[index--];
                } else {
                    break;
                }
            }
            arr[index+1] = tmp;
        }
    }
}
